package com.bigshen.algorithm.iHash.solution03LongestSubstringWithoutRepeatCharacter;

import java.util.HashMap;
import java.util.Map;

/**
 * 3. Longest Substring Without Repeating Characters
 *
 * Given a string s, find the length of the longest substring without repeating characters.
 *
 * Example 1:
 * Input: s = "abcabcbb"
 * Output: 3
 * Explanation: The answer is "abc", with the length of 3.
 *
 * Example 2:
 * Input: s = "bbbbb"
 * Output: 1
 * Explanation: The answer is "b", with the length of 1.
 *
 * Example 3:
 * Input: s = "pwwkew"
 * Output: 3
 * Explanation: The answer is "wke", with the length of 3.
 * Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
 *
 * Example 4:
 * Input: s = ""
 * Output: 0
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (null == s || s.length() == 0) {
            return 0;
        }
        char[] array = s.toCharArray();
        int maxLength = 0;
        int length = 0;
        Map<Character, Integer> map = new HashMap<>(); // 存储字符 + 所处下标
        for (int i = 0; i < array.length; i ++) {
            if (map.containsKey(array[i])) {
                // 出现重复字符，统计长度
                maxLength = Math.max(maxLength, length);
                // 重置长度
                length = i - map.get(array[i]);
                map = new HashMap<>();
            } else {
                length += 1;
            }
            map.put(array[i], i);
        }
        maxLength = Math.max(maxLength, length);
        return maxLength;
    }
}
